import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName Offer06
 * @Description 剑指 Offer 06. 从尾到头打印链表
 * @Author clockTown
 * @Date 2021/8/13 15:51
 * @Version 1.0
 */


class Offer06 {
}

class Offer06V0 {
    /**
     * v0 使用栈存储并翻转元素顺序
     */
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new LinkedList<>();

        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }

        int[] res = new int[stack.size()];
        int i = 0;
        while (!stack.isEmpty()){
            res[i++] = stack.pop();
        }
        return res;
    }

}
class Offer06V1 {
    /**
     * v1 使用ArrayList存储元素，最后翻转为数组
     */
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (head != null) {
            arrayList.add(head.val);
            head = head.next;
        }
        int[] res = new int[arrayList.size()];
        int i = 0;
        int l = arrayList.size() - 1;
        while (i < arrayList.size()){
            res[i++] = arrayList.get(l--);
        }
        return res;
    }

}
class Offer06V2 {
    /**
     * 题解思路：不借助其他数据结构的方法，先遍历一遍链表获得链表长度，然后将链表的值反序填充到数组
     */
    public int[] reversePrint(ListNode head) {
        //先获取链表长度，创建对应长度数组
        ListNode currNode = head;
        int len = 0;
        while(currNode != null){
            len ++;
            currNode = currNode.next;
        }
        int[] result = new int[len];

        //再次遍历链表，将值倒序填充至结果数组
        currNode = head;
        while(currNode != null){
            result[len - 1] = currNode.val;
            len --;
            currNode = currNode.next;
        }
        return result;
    }
}






